This invention relates to a buffer storage control apparatus for use in an electronic data processing (EDP) system.
Buffer storage techniques have been used to reduce the effective access time for main memory unit (MMU) or input/output (I/O) storage units. In a practical EDP system designed to achieve a shorter access time, a high-speed random access memory (RAM) unit is provided at a central processing unit (CPU) as a buffer storage unit to store frequently used data. The buffer storage unit serves to greatly reduce the access time as compared to the system only using the MMU. One example of such a configuration is described in a paper by Harry Katzan, Jr., entitled "Storage Hieraarchy Systems," proceedings of the Spring Joint Computer Conference, 1971, pp. 325-336.
However, since such a buffer storage unit is costly, its storage capacity is not large enough to have a complete copy of all the contents stored in the MMU. Therefore, to store new data in the buffer storage unit, an old block of data stored in said storage unit must be replaced. Known alogorithms for data block (referred to simply as "block" hereunder) replacement include the random replacement (RR) alogrithm for replacing blocks at random, the first-in-first-out (FIFO) algorithm for replacing the block stored first, and the least-recently used (LRU) algorithm for replacing the oldest block at the time of the final reference. For details of these algorithms, reference can be made to a paper by J. Gecsei, D. R. Slutz and I. L. Traiger, entitled "Evaluation Techniques For Storage Hierarchies," IBM Systems Journal, No. 2, 1970, pp. 78-117.
Under particular conditions, cases exist where a block once read out of the buffer is seldom used afterwards. For example, when a designated block in the MMU is transferred from its input area to its user area by the use of an I/O supervisor program, all the data stored in the corresponding block in a buffer storage unit is no longer needed. For this reason, more efficient use of the buffer storage unit can be achieved by replacing the corresponding block rather than by replacing the first-used block, for example. Also, if data words are sequentially read out of a disk storage unit in the order of the disk sector or cylinder and, as a result, all the data words in the corresponding block in the buffer storage unit are read out therefrom, it is more efficient to replace such a block in place of the first-used block, for example. In either case, none of the conventional algorithms are effective. More specifically, by the use of the RR algorithm, replacement is performed randomly; by the FIFO algorithm, the first stored block is replaced regardless of whether not it is read out, and finally, by the LRU algorithm, the least-recently used block is replaced. In each case, a necessary block rather than an unnecessary block may be replaced using the conventional techniques.